1. Field of the Invention
This invention relates to computer modelling for process control, and more particularly relates to computer modelling of the process of shaping a geometric object by controlled cumulative translational sweeps, according to a parameterized operational rayset, to provide a model of shaping changes to the object during the process.
2. Description of the Prior Art
The following publications and patents are representative of the prior art:
Publications
Koppelman, G. M., Wesley M.A., "OYSTER: A Study of Integrated Circuits as Three-Dimensional Structures," IBM Journal of Research and Development, 27(2) (1983), pp. 149-163, shows semiconductor fabrication sequences using polyhedral modelling systems. PA1 Wesley, M. A., Lozano-Perez, T., Lieberman, L. T., Lavin, M. A. and Grossman, D. D., "A geometric modelling system for automated mechanical assembly," IBM Journal of Research and Development, 24(1) (1980), pp. 64-74, shows a technique for designing " . . . objects by combining positive and negative parameterized primitive volumes . . . represented internally as polyhedra." PA1 Rossignac, J. R., and Requicha, A. A. G., "Offsetting Operations in Solid Modelling," Computer Aided Geometric Design, 3(1986), pp. 129-148, North Holland, shows how sequences of solid offsetting operations can be used to develop solid models having surface "blends" made through the generation of constant-radius "fillets" and "rounds." PA1 Rossignac, J. R., "Blending and Offsetting Solid Models," TM 54 Production Automation Project (also Ph. D. Dissertation), University of Rochester, June 1985, shows shaping techniques including general offsetting techniques leading beyond the polyhedral domain. PA1 Farouki, R. T., "The Approximation of Non-degenerate Offset Surfaces," Computer Aided Geometric Design 3 (1986) pp. 15-43, North Holland, shows shaping techniques including general offsetting techniques leading beyond the polyhedral domain. PA1 Farouki, R. T., "Exact Offset Procedures for Simple Solids," Computer Aided Geometric Design 2 (1985), pp. 257-279, North Holland, shows polyhedral offsetting applied to convex polyhedra. PA1 Chazelle, B "Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm," SIAM J. Comput. 13 (3) (1984) pp. 488-507, a method for splitting general polyhedra into convex components that are separately shaped and reassembled. PA1 Lozano-Perez, T. and Wesley, M. "An algorithm for planning collision-free paths among polyhedral obstacles," Comm. ACM, shows a collision avoidance algorithm for a polyhedral object moving among known polyhedral obstacles, using a calculated sweep, check for collisions, and proposed new path. PA1 Korein, J. U. "A geometric Investigation of Reach," ACM Distinguished Dissertation, MIT Press, 1985, shows sweeping to computer the shape of various space regions. PA1 Lozano-Perez, T. "Spatial Planning: Configurations Space Approach," IEEE Transactions on Computers C-32 (2) (1983), shows the use of unions of convex polyhedra in computing collision-free robotic motions. PA1 Dally, W. J., Donath, W., and Ling, D., "Fast Convolution Operation for Contact Verification in Integrated Circuits" IBM Technical Disclosure Bulletin Vol. 28 No. 12, May 1986, shows convolution techniques, using convex polygons, for contact verification in integrated circuits. PA1 Coxeter, H. S. M. "Regular Polytopes," Dover Publications 1973, pp. 27-30. PA1 Fedorov, E. S., "Elemente der Gestaltenlehre," Mineralogicheskoe obshchestvo Leningrad (2), 21 (1885), pp. 1-279, is an early text in the mathematics. PA1 Grunbaum, B. "Convex Polytopes," Interscience Publishers 1967, explains polytopes. PA1 McMullen, P., "On Zonotopes," trans. Amer. Math. Soc., 159 (1971), pp. 91-109, explains zonotopes. PA1 Serra, J., "Image Analysis and Mathematical Morphology," Academic Press 1982, pp. 47-48, shows the algebraic properties of dilation and erosion operations on neighborhoods as discrete domains such as the pixels in an image. Some sequences of these operations are expressible as Minkowski sums. Erosion, for example, need not be a simple operation such as the sandblasting of a film of dirt, but rather may be made by erosion with a convex structuring element such as a regular hexagon; that is, by taking out bites that are shaped like regular hexagons. Serra states that he can " . . . erode a 3-D set X . . . with respect to a polyhedron B, by combining 2-D erosions." Serra does not suggest using iterated sweep sequences for growing, shrinking and rounding polyhedrons. Serra develops the algebraic properties of "dilation" and "erosion" --shaping operations based on neighborhood rules applicable over discrete domains, such as the arrangement of pixels in an image. PA1 Sternberg, Stanley R., "An Overview of Image Algebra and Related Architectures," in "Integrated Technology for Parallel Image Processing," Academic Press," 1985, pp. 79-100. PA1 Schneider, R. and Weil. Woflgang "Zonoids and Related Topics," in "Convexity and Its Applications," edited by Peter Gruber and Jorg Wills, Birkhauser 1983, pp. 296-317, explains zonoids. PA1 Betke, U. and McMullen, P., "Estimating the size of convex bodies from projections," J. London Math. Soc. (2), 27 (1983), pp. 525.538. shows the use of zonotopes to approximate spheres. PA1 U.S. Pat. No. 3,519,997, Bernhart et al, PLANAR ILLUSTRATION METHOD AND APPARATUS, 1970, shows computer techniques for making 2-D graphics of 3D objects, converting Cartesian coordinates and projections in separate subroutines. PA1 U.S. Pat. No. 4,212,009, Adleman et al, SMOOTHING A RASTER DISPLAY, 1980, shows sweeping a geometric shape by sampling, growing and eroding. PA1 U.S. Pat. No. 4,300,136, Tsuiki et al, DISPLAY PATTERN PREPARING SYSTEM, 1981, shows a technique for assembling a display from segments stored as fixed patterns and reference positions. PA1 U.S. Pat. No. 4,454,507, Srinavasan et al, REAL-TIME CURSOR GENERATOR, 1984, shows synthesis of a cursor on a display by specifying start and stop and number of raster lines. PA1 U.S. Pat. No. 4,510,616, Lougheed et al, DESIGN RULE CHECKING USING SERIAL NEIGHBORHOOD PROCESSORS, shows the use of an array processor to examine 3.times.3 neighborhood segments of an image for compliance to design rules for laying out integrated circuits. PA1 U.S. Pat. No. 4,569,014, Kishi et al, METHOD OF CREATING A CURVED SURFACE, 1986, shows development of a curved surface in sections from section data by developing perpendicular curves for machining control.
Foreign Patents
France No. 1,494,849, PROCESS FOR GENERATION OF A CURVE FOR MACHINES TO TRACE OR TO USE, 1966, shows a computer technique to develop curves by combining segments.
U.S. Patents
"Shaping" is a generic term in geometric modelling, having many senses such as growing, shrinking, rounding, filleting, faceting, blending and smoothing. It is encountered in such applications as: growing and shrinking to solve the collision-avoidance problem; growing and shrinking for the generation of blends; sweeping to compute the shape of various space regions; and offsetting as a means of defining mechanical tolerance.
Sweeping, as a geometric modelling tool, refers in its broad sense to the tracking of a body's motion in space. Most modellers can compute the track or sweptspace of a moving body which does not tumble, i.e., which has only translational freedom; this is the region of space that the moving body has passed through, or, quite informally, its "ghost." Some modellers can approximate tumbling motions (rotational freedom) as well.